Covering with blocks in the non-symmetric case

Considering an infinite string of i.i.d. random letters drawn from a finite alphabet we define the cover timeW _n as the number of random letters needed until each pattern of lenghtn appears at least once as a substring. Sharp weak and a.s. limit results onW _n are known in the symmetric case, i.e., when the random letters are uniformly distributed over the alphabet. In this paper we determine the limit distribution ofW _n in the nonsymmetric case asn. Generalizations in terms of point processes are also proved.Dedicated to Endre Csáki on his 60th birthday.     

Self-avoiding walks on random fractal environments

Self-avoiding random walks (SAWs) are studied on several hierarchical lattices in a randomly disordered environment. An analytical method to determine whether their fractal dimensionD _saw is affected by disorder is introduced. Using this method, it is found that for some lattices,D _saw is unaffected by weak disorder; while for othersD _saw changes even for infinitestimal disorder. A weak disorder exponent is defined and calculated analytically [ measures the dependence of the variance in the partition function (or in the effective fugacity per step)vL on the end-to-end distance of the SAW,L]. For lattices which are stable against weak disorder (<0) a phase transition exists at a critical valuev=v ^* which separates weak- and strong-disorder phases. The geometrical properties which contribute to the value of are discussed.     

Critical behavior of self-avoiding walks on fractals

Using a new graph counting technique suitable for self-similar fractals, exact 18th-order series expansions for SAWs on some Sierpinski carpets are generated. From them, the critical fugacityx _c and critical exponents _SAW and _SAW are obtained. The results show a linear dependence of the critical fugacity with the average number of bonds per site of the lattices studied. We find for some carpets with low lacunarity that _SAW<0.75, thus violating the relation _SAW(fractal) > _SAW (d) for SAWs on the fractals which are embedded in ad-dimensional Euclidean space.     

On the origin of bursts and heavy tails in animal dynamics

Over recent years there has been an accumulation of evidence that many animal behaviours are characterised by common scale-invariant patterns of switching between two contrasting activities over a period of time. This is evidenced in mammalian wake-sleep patterns, in the intermittent stop-start locomotion of Drosophila fruit flies, and in the Lévy walk movement patterns of a diverse range of animals in which straight-line movements are punctuated by occasional turns. Here it is shown that these dynamics can be modelled by a stochastic variant of Barabási’s model [A.-L. Barabási, The origin of bursts and heavy tails in human dynamics, Nature 435 (2005) 207-211] for bursts and heavy tails in human dynamics. The new model captures a tension between two competing and conflicting activities. The durations of one type of activity are distributed according to an inverse-square power-law, mirroring the ubiquity of inverse-square power-law scaling seen in empirical data. The durations of the second type of activity follow exponential distributions with characteristic timescales that depend on species and metabolic rates. This again is a common feature of animal behaviour. Bursty human dynamics, on the other hand, are characterised by power-law distributions with scaling exponents close to −1 and −3/2.     

Quenched Averages for Self-Avoiding Walks and Polygons on Deterministic Fractals

We study rooted self avoiding polygons and self avoiding walks on deterministic fractal lattices of finite ramification index. Different sites on such lattices are not equivalent, and the number of rooted open walks W _n (S), and rooted self-avoiding polygons P _n (S) of n steps depend on the root S. We use exact recursion equations on the fractal to determine the generating functions for P _n (S), and W _n(S) for an arbitrary point S on the lattice. These are used to compute the averages ,, and over different positions of S. We find that the connectivity constant μ, and the radius of gyration exponent are the same for the annealed and quenched averages. However, , and , where the exponents and , take values different from the annealed case. These are expressed as the Lyapunov exponents of random product of finite-dimensional matrices. For the 3-simplex lattice, our numerical estimation gives and , to be compared with the known annealed values and .     

Law of large numbers for increasing subsequences of random permutations

Let the random variable Z_n,k denote the number of increasing subsequences of length k in a random permutation from S_n, the symmetric group of permutations of {1,…,n}. We show that Var(Z) = o((EZ)²) as n → ∞ if and only if . In particular then, the weak law of large numbers holds for Z if ; that is, We also show the following approximation result for the uniform measure U_n on S_n. Define the probability measure μ on S_n by where U denotes the uniform measure on the subset of permutations that contain the increasing subsequence {x₁,x₂,…,x}. Then the weak law of large numbers holds for Z if and only if where ∣∣˙∣∣ denotes the total variation norm. In particular then, (*) holds if . In order to evaluate the asymptotic behavior of the second moment, we need to analyze occupation times of certain conditioned two‐dimensional random walks. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Diameter of random spanning trees in a given graph

Motivated by the observation that the sparse tree‐like subgraphs in a small world graph have large diameter, we analyze random spanning trees in a given host graph. We show that the diameter of a random spanning tree of a given host graph G is between and with high probability., where c and c′ depend on the spectral gap of G and the ratio of the moments of the degree sequence. For the special case of regular graphs, this result improves the previous lower bound by Aldous by a factor of logn. Copyright © 2011 John Wiley Periodicals, Inc. J Graph Theory 69: 223–240, 2012     

Phase transitions for random walk asymptotics on free products of groups

Suppose we are given finitely generated groups Γ₁,…,Γ_m equipped with irreducible random walks. Thereby we assume that the expansions of the corresponding Green functions at their radii of convergence contain only logarithmic or algebraic terms as singular terms up to sufficiently large order (except for some degenerate cases). We consider transient random walks on the free product Γ₁* … *Γ_m and give a complete classification of the possible asymptotic behaviour of the corresponding n‐step return probabilities. They either inherit a law of the form ?^nδn log n from one of the free factors Γ_i or obey a ?^nδn^?3/2‐law, where ? < 1 is the corresponding spectral radius and δ is the period of the random walk. In addition, we determine the full range of the asymptotic behaviour in the case of nearest neighbour random walks on free products of the form $\mathbb{Z}^{d_1}\ast \ldots \ast \mathbb{Z}^{d_m}Suppose we are given finitely generated groups Γ₁,…,Γ_m equipped with irreducible random walks. Thereby we assume that the expansions of the corresponding Green functions at their radii of convergence contain only logarithmic or algebraic terms as singular terms up to sufficiently large order (except for some degenerate cases). We consider transient random walks on the free product Γ₁* … *Γ_m and give a complete classification of the possible asymptotic behaviour of the corresponding n‐step return probabilities. They either inherit a law of the form ?^nδn log n from one of the free factors Γ_i or obey a ?^nδn^?3/2‐law, where ? < 1 is the corresponding spectral radius and δ is the period of the random walk. In addition, we determine the full range of the asymptotic behaviour in the case of nearest neighbour random walks on free products of the form $\mathbb{Z}^{d_1}\ast \ldots \ast \mathbb{Z}^{d_m}$. Moreover, we characterize the possible phase transitions of the non‐exponential types n log n in the case Γ₁ * Γ₂. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

基于分离粒子随机扩散理论的色谱模拟

为了对扩散分子的轨迹实施动态追踪与模拟, 深入理解分子扩散对色谱动力学的影响, 本文利用微尺度受限空间随机行走的模拟方法对色谱填充柱中的分子扩散过程进行了模拟. 重点考察了固定相的填充率、固定相的形状和柱长对色谱动力学行为的影响. 模拟结果表明短柱和大填充率具有较高的柱效; 在相同的密堆排列下, 固定相形状对分子扩散过程影响微弱; 待分离粒子的运动表现出微尺度空间限域的扩散特征, 但粒子的流动行为会随外部压力的增大而增加. 本论文提出的模拟方法对于发展高效能色谱, 开发新型分离技术等具有参考意义.     

Fractional motions

Brownian motion is the archetypal model for random transport processes in science and engineering. Brownian motion displays neither wild fluctuations (the “Noah effect”), nor long-range correlations (the “Joseph effect”). The quintessential model for processes displaying the Noah effect is Lévy motion, the quintessential model for processes displaying the Joseph effect is fractional Brownian motion, and the prototypical model for processes displaying both the Noah and Joseph effects is fractional Lévy motion. In this paper we review these four random-motion models–henceforth termed “fractional motions” –via a unified physical setting that is based on Langevin’s equation, the Einstein–Smoluchowski paradigm, and stochastic scaling limits. The unified setting explains the universal macroscopic emergence of fractional motions, and predicts–according to microscopic-level details–which of the four fractional motions will emerge on the macroscopic level. The statistical properties of fractional motions are classified and parametrized by two exponents—a “Noah exponent” governing their fluctuations, and a “Joseph exponent” governing their dispersions and correlations. This self-contained review provides a concise and cohesive introduction to fractional motions.